/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-28 16:49:27
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-28 17:37:40
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/408_str/2018.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>

/**
 * 暴力解法 O(N^2)
 * 从最小正整数1开始，跟数组中每个元素进行比较
 * 比较有两者情况 
 *  1.跟数组中某个元素相等，代表该元素出现，则退出该循环，从i+1重新对比
 *  2.for循环结束退出，表示i没有在数组中出现，则i就是最小正整数
 *  最后整个大循环退出，表示数组是连着的(例如1，2，3，4)则推出后最小整数就是5
 */
int find_min_int(int arr[],int n)
{
    int j;
    for(int i = 1; i <= n; i++)
    {
        for(j = 0; j < n; j++)
        {
            if(arr[j] == i)
                break;
        }
        if(j == n)
            return i;
    }
    return n+1;
}

int find_min_int_to_hash(int arr[],int n)
{
    //   0   1   2   3   4   5   6
    //{ -1,  0,  1,  2,  3,  4,  5}
    int* m_hash = new int(n);
    for(int i = 0; i < n; i++)
    {
        if(arr[i] >0 && arr[i] <= n)
        {
            m_hash[arr[i] - 1] = 1;
        }
    }
    for(int j = 0; j < n; j++)
    {
        if(m_hash[j] == 0)
            return j + 1;
    }
    return n+1;
}

int main()
{
    //int arr[] = {-1,-2,-5,0,2,4,3,1};
    int arr[] = {-1,0,1,3,-4,4,5};
    int n = sizeof(arr) / sizeof(arr[0]);
    // int t = find_min_int(arr,n);
    int t = find_min_int_to_hash(arr,n);
    std::cout << t << std::endl;
    return 0;
}